\subsection{Local Search}
\label{subsec:local-search}

Another interesting approach to this problem is local search. Local search
starts at some initial assignment or state, it then picks a neighboring
assignment, evaluates if this new assignment is an improvement and decides
whether to move into the neighbor assignment. This is then repeated a number of
times until a good solution is found, the process stops improving or the
algorithm is terminated for other reasons. To evaluate if one assignment is
better or worse than another, and whether it is close to an optimal solution, a
cost function is used to evaluate each assignment. Thus there are four central
elements to define for the local search approach. A state (see
Sec. \ref{subsec:assignment}, a neighborhood of a state, a cost function and an
algorithm to guide the movement between states.


\subsubsection{Building The Neighborhood}
\label{subsubsec:neighborhood} 

A central part of any local search is defining which states are 
neighbors. In our case an assignment consists of $\sim 50.000$ integer 
values representing the number of people on duty at a given time slot, 
department and type. We could define $A'$ to be the neighbor of $A$ if 
$A'$ can be reached by changing any number of integers in $A$ to any 
value. This would certainly ensure that the global optimal assignment 
can be reached, but it would also reduce the local search to a brute 
force algorithm by making it evaluate all possible assignments. We need 
to limit the neighborhood in a way that minimizes the chance of getting 
stuck in a local minimum while at the same time is not too large to allow 
the search to proceed at an acceptable pace. 

One option is to randomly generate a neighborhood. While this is 
programmatically easy, the downside of this approach is that we know 
nothing about the quality of our neighborhood. This would make it hard 
for the algorithm to actually find good local maxima, as we would 
basically be navigating blindly. 

Instead, we will generate neighbor states by using another algorithm to 
build a neighborhood that is likely to be an improvement over the 
current assignment. First, we need to define when an assignment is a 
neighbor to another assignment. 

Let $A$ and $A'$ be assignments of type \textit{Schedule}. $A'$ is a 
neighbor of $A$ iff in $A'$ all shifts of exactly one type on one day are moved 
from one department to at most two other departments. For brevity, 
we regard this relation between $A$ and $A'$ as $A \sim A'$. Note that 
this definition of neighborhood is asymmetric, as $A' \sim A$ doesn't 
hold after our definition because shifts can be split up, but not unioned again. 

Using this definition of a neighbor, we can see that the neighborhood is 
of size $T\cdot Z$, where $T$ is the number of types of shifts and $Z$ 
the number of days. To generate a new neighborhood, we apply the 
algorithm outlined in Fig \ref{fig:neighbor}. 

\begin{figure}[t] 

  \centering \begin{algorithmic} 

    \STATE \textbf{PROCEDURE} Generate-Neighborhood(Assignment $A$) \textbf{returns} Neighborhood:
    
    \STATE let $N \leftarrow$ empty Neighborhood
    \STATE let $D \leftarrow$ set of departments $\in A$
    \STATE let $T \leftarrow$ set of types of shifts $\in A$
    \STATE let $Z \leftarrow$ set of days $\in A$
    
    \FORALL{$t \in T$}
    \STATE let $max_D \leftarrow d \in D$ department with the most shifts of $t$
    \STATE let $min_{D1}, min_{D2} \leftarrow d \in D$ departments with the fewest shifts of $t$
    \FORALL{$z \in Z$} 
    \STATE $N \leftarrow N \cup \{A'$ of $A$ where all shifts of $t$ on $z$ are
    distributed from $max_D$ to $min_{D1}, min_{D2}\}$
    \ENDFOR
    \ENDFOR 
    
    \RETURN{N}
  \end{algorithmic} 

  \caption{The procedure to generate a neighborhood for an assignment 
  $A$.}
  \label{fig:neighbor} 
\end{figure} 

Rephrasing Fig. \ref{fig:neighbor} in plain English, the algorithm finds the two
departments with the fewest shifts of a type over the entire quarter, and the
department with the most. It then creates a neighbor assignment for each day of
the schedule, where shifts are reassigned from the department with the most
assignment to departments with the fewest. As shifts are being distributed more
equally than already in the current assignment, this will build up a good
neighborhood.

\subsubsection{Simulated Annealing} 

Simulated annealing is a variant of local search that allows the search 
algorithm to accept worse assignments than the current assignment based 
on how long it has been running already \cite{kleinberg_algorithm_2005}. 

The initial assignment is a schedule where the entire demand has been assigned
to one single department (see Sec. \ref{subsubsec:datastruct}). Via a
neighbor generating function (see Sec.  \ref{subsubsec:neighborhood}), we
generate a neighbor for each iteration of the local search. If the neighbor is
an improvement over the previous assignment it is selected. If it is not an
improvement it can still be selected with a probability that decreases in each
iteration of the search.

This rather simple approach enables us to find good global assignments in the
assignment space and to approximate good solutions in reasonable time. The main
concern is the cost function that needs to be run for each neighbor in the
neighborhood of the current assignment and for each iteration in the local
search (see Sec. \ref{subsubsec:cost} for details on the cost function we
employ).
